package com.uhu.code;

import java.util.*;

/**
 * 56. 合并区间
 * https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked
 */
public class Solution56 {
    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, Comparator.comparingInt(v -> v[0]));
        int[][] result = dmerge(intervals);
        return result;
    }

    private int[][] dmerge(int[][] intervals) {
        Set<Integer> eq = new HashSet<>();
        eq.add(0);
        for(int i = 1; i < intervals.length; i++) {
            int [] lastArea = intervals[i - 1];
            int [] nowArea = intervals[i];
            if((lastArea[0] >= nowArea[0] && lastArea[0] <= nowArea[nowArea.length - 1]) || (lastArea[lastArea.length - 1] >= nowArea[0] && lastArea[lastArea.length - 1] <= nowArea[nowArea.length - 1]) || (nowArea[0] >= lastArea[0] && nowArea[0] <= lastArea[lastArea.length - 1]) || (nowArea[nowArea.length - 1] >= lastArea[0] && nowArea[nowArea.length - 1] <= lastArea[lastArea.length - 1])) {
                // 合并
                intervals[i] = new int[] {Math.min(lastArea[0], nowArea[0]), Math.max(lastArea[lastArea.length -1], nowArea[nowArea.length -1])};
                // 记录合并后位置
                eq.add(i);
                // 移除无效位置
                eq.remove(i - 1);
            }else {
                // 记录合并后位置
                eq.add(i - 1);
                // 记录当前位置
                eq.add(i);
            }
        }
        int[][] result = new int[eq.size()][];
        int k = 0;
        for (int i = 0; i < intervals.length; i++) {
            if(eq.contains(i)) {
                result[k] = intervals[i];
                k++;
            }
        }
        if(result.length == intervals.length) {
            return result;
        }
        return dmerge(result);
    }
}
